home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_11_02 / 1102091a < prev    next >
Text File  |  1992-12-06  |  2KB  |  55 lines
  1. /*
  2.  *
  3.  * Minimum comparison network pairs
  4.  */
  5.  
  6. /* 10 items - 29 comparisons; 9 - 25 */
  7. int net10[29][2] = {
  8.     {2,9},{1,5},{6,10},{3,7},{4,8},{1,4},{7,10},{3,6},
  9.     {1,2},{4,7},{9,10},{5,8},{1,3},{5,9},{2,6},{8,10},
  10.     {2,3},{4,5},{6,7},{8,9},{2,4},{7,9},{3,5},{6,8},
  11.     {3,4},{7,8},{4,6},{5,7},{5,6}};
  12.  
  13. /* 12 items - 39 comparisons; 11 - 35 */
  14. int net12[39][2] = {
  15.     {1,2},{3,4},{5,6},{7,8},{9,10},{11,12},{2,4},{6,8},
  16.     {10,12},{1,3},{5,7},{9,11},{2,3},{6,7},{10,11},
  17.     {2,6},{7,11},{6,10},{3,7},{2,6},{7,11},{1,5},{8,12},
  18.     {4,8},{5,9},{1,5},{8,12},{2,5},{8,11},{4,9},{3,4},
  19.     {9,10},{3,5},{8,10},{4,6},{7,9},{4,5},{6,7},{8,9}};
  20.  
  21. /* 16 items - 60 comparisons; 15 - 56; 14 - 51; 13 - 46 */
  22. int net16[60][2] = {
  23.     {1,2},{3,4},{5,6},{7,8},{9,10},{11,12},{13,14},
  24.     {15,16},{1,3},{5,7},{9,11},{13,15},{2,4},{6,8},
  25.     {10,12},{14,16},{1,5},{9,13},{2,6},{10,14},{3,7},
  26.     {11,15},{4,8},{12,16},{1,9},{2,10},{3,11},{4,12},
  27.     {5,13},{6,14},{7,15},{8,16},{6,11},{7,10},{4,13},
  28.     {8,12},{14,15},{2,3},{5,9},{2,5},{8,14},{3,9},
  29.     {12,15},{3,5},{6,7},{10,11},{12,14},{4,9},{8,13},
  30.     {7,9},{4,6},{8,10},{11,13},{4,5},{6,7},{8,9},{10,11},
  31.     {12,13},{7,8},{9,10}};
  32.  
  33. /*
  34.  * Extracts a network for n items from an array of
  35.  * comparison pairs for m items when n <= m.  Expects
  36.  * the 2nd member of each pair to be the larger.  For
  37.  * example, to extract a minimum comparison network
  38.  * for 9 items call
  39.  *  extract(9, sizeof(net10)/(2*sizeof(int)), net10);
  40.  */
  41. extract(n, m, network)
  42. int n, m;
  43. int network[][2];
  44. {
  45.     int i;
  46.  
  47.     for(i = 0; i < m; i += 1)
  48.     {
  49.         if(network[i][1] <= n)
  50.             printf("swap(%d, %d);\n",
  51.                 network[i][0], network[i][1]);
  52.     }
  53. }
  54.  
  55.